package sort.onlogn.my_quick_sort_test;

import java.util.Arrays;
import java.util.Random;

/**
 * @author yeyangtao created at 11:36 2021/1/22
 */
public class QuickSort20210122 {
    public static void main(String[] args) {
        int[] data = new Random()
                .ints(0, 100)
                .limit(20)
                .toArray();
        System.out.println(Arrays.toString(data));
        quickSort(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }

    private static void quickSort(int[] data, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(data, left, right);
        quickSort(data, left, p - 1);
        quickSort(data, p + 1, right);
    }

    private static int partition(int[] data, int left, int right) {
        int p = data[right];
        int i = left;
        for (int j = left; j <= right; j++) {
            if (data[j] < p) {
                if (i != j) {
                    int temp = data[i];
                    data[i] = data[j];
                    data[j] = temp;
                }
                i++;
            }
        }
        data[right] = data[i];
        data[i] = p;
        return i;
    }
}
